"""
1. 找到待排序列表中的最大值 k，开辟一个长度为 k+1 的计数列表，计数列表中的值都为 0。

2. 走访待排序列表，如果走访到的元素值为 i，则计数列表中索引 i 的值加1。

3. 走访完整个待排序列表，计数列表中索引 i 的值 j 表示 i 的个数为 j，统计出待排序列表中每个值的数量。

4. 创建一个新列表，遍历计数列表，依次在新列表中添加 j 个 i，新列表就是排好序后的列表，整个过程没有比较待排序列表中的数据大小。


局限性：
    1.当数列最大和最小值差距过大时，并不适合用计数排序。
        例如，给出 20个 随机整数，范围在 0到1亿 之间，这时如果使用计数排序，需要创建长度为1亿的数组。
        不但严重浪费空间，而且时间复杂度也会随之升高。

    2.当数列元素不是整数时，也不适合用计数排序。
        如果数列中的元素都是小数，如 25.213 或 0.00000001 这样的数字，则无法创建对应的统计数组。
        这样显然无法进行计数排序。
"""


def count_sort(array):
    """
    初步实现代码
    :param array:
    存在的问题：只以数列的最大值来决定统计数组的长度，其实并不严谨
        例如下面的数列：
            95，94，91，98，99，90，99，93，91，92
        这个数列的最大值是99，但最小的整数是90。
        如果创建长度为100的数组，那么前面从0到89的空间位置就都浪费了！
    """
    # 1.得到数列的最大值
    max_value = array[0]
    for i in range(1, len(array)):
        if array[i] > max_value:
            max_value = array[i]
    # 2.根据数列的最大值确定统计数组的长度
    count_array = [0] * (max_value + 1)
    # 3.遍历数列，填充统计数组
    for i in range(0, len(array)):
        count_array[array[i]] += 1
    # 4.遍历统计数组，输出结果
    sorted_array = []
    for i in range(0, len(count_array)):
        for j in range(0, count_array[i]):
            sorted_array.append(i)
    return sorted_array


def count_sort_v2(array):
    """
    只要不再以输入数列的最大值+1作为统计数组的长度，而是以数列最大值-最小值+1作为统计数组的长度即可。
    同时，数列的最小值作为一个偏移量，用于计算整数在统计数组中的下标。
    以 95，94，91，98，99，90，99，93，91，92 为例，
    统计出数组的长度为 99-90+1=10，偏移量等于数列的最小值90。
    对于第1个整数95，对应的统计数组下标是95-90=5，

    此外，朴素版的计数排序只是简单地按照统计数组的下标输出元素值，并没有真正给原始数列进行排序。
    如果只是单纯地给整数排序，这样做并没有问题。
    但如果在现实业务里，例如给学生的考试分数进行排序，遇到相同的分数就会分不清谁是谁。

        举例说明：
            姓名      成绩
            小灰      90
            小黄      99
            小红      95
            小白      94
            小绿      95

    给出一个学生成绩表，要求按成绩从低到高进行排序，如果成绩相同，则遵循原表固有顺序。
    那么，当我们填充统计数组以后，只知道有两个成绩并列为95分的同学，却不知道哪一个是小红，哪一个是小绿
    :param array:
    :return:
    """
    # 1.得到数列的最大值最小值，并计算出差值d
    max_value = array[0]
    min_value = array[0]
    for i in range(1, len(array)):
        if array[i] > max_value:
            max_value = array[i]
        if array[i] < min_value:
            min_value = array[i]
    d = max_value - min_value
    # 2.创建统计数组并统计对应的元素个数
    count_array = [0] * (d + 1)
    for i in range(0, len(array)):
        count_array[array[i] - min_value] += 1
    # 3.统计数组做变形，后面的元素等于前面的元素之和
    for i in range(1, len(array)):
        count_array[i] += count_array[i - 1]
    # 4.倒序遍历原始数组，从统计数组找到正确位置，输出到结果数组
    sorted_array = [0] * len(array)
    for i in range(len(array) - 1, -1, -1):
        sorted_array[count_array[array[i] - min_value] - 1] = array[i]
        count_array[array[i] - min_value] -= 1
    return sorted_array


my_array = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10]
print(count_sort(my_array))